package 剑指offer;

import java.util.HashMap;
import java.util.Map;

public class _07重建二叉树 {
	public static void main(String[] args) {
		int pre[]=new int[] {1,2,3};
		int inor[]=new int[]{3,2,1};
		 System.out.println(buildTree(pre,inor));
	}
	 public static TreeNode buildTree(int[] preorder, int[] inorder) {
		 HashMap<Integer, Integer> indexMap=new HashMap<Integer, Integer>();
		 for (int i = 0; i < inorder.length; i++) {
			indexMap.put(inorder[i],i);
		}
		 return helpNode(preorder, 0,preorder.length-1, 0,preorder.length-1,indexMap);
	    }
	 /**
	  * 
	  *@time 2021年1月4日上午10:25:51
	  * 
	  *@param preorder
	  *@param preStart
	  *@param preEnd
	  *@param inStart
	  *@param inEnd
	  *@param indexMap
	  *@return TreeNode
	  *
	  *@see 递归的方法求解
	  * 前提是不重复的元素重建二叉数
	  */
	 public static TreeNode helpNode(int[] preorder, int preStart,int preEnd,int inStart,int inEnd,Map<Integer,Integer>indexMap) {
		 if(preStart>preEnd) return null;
		 int rootval=preorder[preStart];
		 int index=indexMap.get(rootval);
		 TreeNode root=new TreeNode(rootval);
		 int leftNodes=index-inStart;
		 int rightNodes=inEnd-index;
		 if(preStart==preEnd) return root;
		 else {
			 root.left=helpNode(preorder,preStart+1,preStart+leftNodes, inStart,index-1,indexMap);
			 root.right=helpNode(preorder,preEnd-rightNodes+1, preEnd,index+1,inEnd,indexMap);
			 return root;
		 }
		 
	    }

}

     
 
